#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <pthread.h>
#include "quicksort.h"


// Estrutura de uma árvore binária
typedef struct stt_tree {
    int *local;
    struct stt_tree *filho_esq;
    struct stt_tree *filho_dir;
} arvore_b;

// Estrutura de controle das threads
typedef struct controle_stc {
    int num_threads;
    int max_threads;
} controle_stc;

// Estrutura de parametro para as threads criadas
typedef struct kdtree_paramm {
    int **p;
    int profundidade;
    int n_pontos;
    int k;
    int id;
} kdtree_paramm;

// variáveis globais
pthread_t *threads;
pthread_mutex_t mutex_resposta;
pthread_mutex_t mutex_controle;
arvore_b **resposta;
controle_stc controle;


// Função principal que constrói uma KD Tree
void* kdtree(void *args) {
    
    kdtree_paramm *arg = args;
    int **p = arg->p;
    int profundidade = arg->profundidade;
    int n_pontos = arg->n_pontos;
    int k = arg->k;
    int id = arg->id;

    int i, j;
    
    if (!p[0])
        return;
    
    // Selecionando o eixo baseado na profundade tal que o eixo circule em
    // torno de todos os valores válidos.
    int eixo;
    eixo = profundidade % k;
    
    // Ordena a lista de pontos
    quick_sort(p, 0, n_pontos-1, eixo);
    
    // Escolhe o ponto medio como o elemento pivo
    int meio;
    meio = n_pontos / 2;
    
    // Determina pontos que vão à direita e à esquerda da sub-árvore
    int **pontos_esq, **pontos_dir;
    pontos_esq = malloc(sizeof(int*) * meio+1);
    pontos_dir = malloc(sizeof(int*) * (n_pontos-meio+1));
    
    // Gera uma nova lista de pontos que irão a esquerda e direita da sub-árvore
    i = 0;
    while (i < meio) {
        pontos_esq[i] = malloc(sizeof(int) * k);
        memcpy(pontos_esq[i], p[i], sizeof(int) * k);
        i++;
    }
    pontos_esq[i] = NULL;
    
    i = 0;
    while (i < n_pontos-meio-1) {
        pontos_dir[i] = malloc(sizeof(int*) * k);
        memcpy(pontos_dir[i], p[i+meio+1], sizeof(int) * k);
        i++;
    }
    pontos_dir[i] = NULL;
    
    // Cria o no e constrói as sub-árvores
    arvore_b *no;
    no = (arvore_b*) malloc(sizeof(arvore_b));
    
    int *valor_meio = malloc(sizeof(int) * k);
    memcpy(valor_meio, p[meio], sizeof(int) * k);
    no->local = valor_meio;
    
    // Desaloca os pontos já utilizados
    for(i = 0; i < n_pontos-1; i++)
        free(p[i]);
    free(p);
    
    // Se puder criar threads para as sub-árvores da esquerda, senão apenas gera
    // uma nova sub-árvore através da recursão
    
    kdtree_paramm *paramm_esq;
    paramm_esq = malloc(sizeof(kdtree_paramm));
    paramm_esq->p = pontos_esq;
    paramm_esq->profundidade = profundidade+1;
    paramm_esq->n_pontos = meio;
    paramm_esq->k = k;
    paramm_esq->id = -1;
    
    if (id == 0)
        printf("Terminou a inicialização\n");
    
    pthread_mutex_lock(&mutex_controle);
        if (controle.num_threads < controle.max_threads && id >= 0) {
            paramm_esq->id = controle.num_threads;
                pthread_create(&threads[controle.num_threads], NULL, kdtree, (void*) paramm_esq);
                controle.num_threads++;
            pthread_mutex_unlock(&mutex_controle);
            printf("Thread %d criando thread %d com %d pontos\n", id, paramm_esq->id, meio);
        } else {
            pthread_mutex_unlock(&mutex_controle);
            no->filho_esq = kdtree((void*) paramm_esq);
        }
    
    // Gera uma sub-árvore atravez da resursão para a esquerda
    
    kdtree_paramm *paramm_dir;
    paramm_dir = malloc(sizeof(kdtree_paramm));
    paramm_dir->p = pontos_dir;
    paramm_dir->profundidade = profundidade+1;
    paramm_dir->n_pontos = n_pontos-meio-1;
    paramm_dir->k = k;
    paramm_dir->id = -2;
    
    no->filho_dir = kdtree((void*) paramm_dir);
    
    // Retorna e liga os nos com o resultados das sub-árvores em nos de controle
    if (id >= 0) { // Se nao gerar uma recursão
        if (paramm_esq->id >= 0) { // Filho da direita nao liga em controle
            pthread_join(threads[paramm_esq->id], NULL);
            printf("Morreu thread %d\n", paramm_esq->id);
            pthread_mutex_lock(&mutex_resposta);
                no->filho_esq = resposta[paramm_esq->id];
                resposta[id] = no;
            pthread_mutex_unlock(&mutex_resposta);
        } else if (id == controle.num_threads-1) {
            pthread_mutex_lock(&mutex_resposta);
                resposta[id] = no;
            pthread_mutex_unlock(&mutex_resposta);
        }
    }
    return no;
}


void main(int argc, char *argv[]) {
    
    FILE *arquivo;
    int **pontos;
    int k = atoi(argv[2]);          // Tamanho da dimensão
    int n_pontos = atoi(argv[3]);   // Número de pontos retirados do arquivo
    
    pthread_mutex_init(&mutex_controle, NULL);
    pthread_mutex_init(&mutex_resposta, NULL);
    
    controle.max_threads = atoi(argv[4]);
    controle.num_threads = 1;
    
    threads = malloc(sizeof(pthread_t) * controle.max_threads);
    resposta = malloc(sizeof(arvore_b*) * controle.max_threads);
    
    // Abrindo arquivo de entrada
    arquivo = fopen(argv[1], "r");
    if (!arquivo) {
        printf("Não foi possível abrir o arquivo\n");
        return;
    } else {
        // Alocando memória Para o vetor de vetores de k dimensões
        pontos = malloc(sizeof(int*) * n_pontos + 1);
    }
    
    // Lendo cada linha da entrada e atribuindo os valores
    int ponto[k], i, j;
    char tempchar[10];
    for (i=0; i<n_pontos; i++) {
        for(j=0; j < k-1; j++)
            fscanf(arquivo, "%d ", &ponto[j]);
        fscanf(arquivo, "%d", &ponto[j]);
        pontos[i] = malloc(sizeof(int) * k);
        for (j=0; j<k; j++)
            pontos[i][j] = ponto[j];
    }
    pontos[i] = NULL;
    
    kdtree_paramm *paramm;
    paramm = malloc(sizeof(kdtree_paramm));
    paramm->p = pontos;
    paramm->profundidade = 0;
    paramm->n_pontos = n_pontos;
    paramm->k = k;
    paramm->id = 0;
    
    pthread_create(&threads[0], NULL, kdtree, (void*) paramm);
    pthread_join(threads[0], NULL);
    
    
    // IMpressão de alguns resultados iniciais
    
    printf("(%d, %d, %d)\n", resposta[0]->local[0], resposta[0]->local[1], resposta[0]->local[2]);
    printf("(%d, %d, %d)\n", resposta[0]->filho_dir->local[0], resposta[0]->filho_dir->local[1], resposta[0]->filho_dir->local[2]);
    printf("(%d, %d, %d)\n", resposta[0]->filho_esq->local[0], resposta[0]->filho_esq->local[1], resposta[0]->filho_esq->local[2]);
}